#include <stdlib.h>
#include <stdio.h>

// Prim算法，生成最小生成树

typedef char VertexType; // 顶点数据类型
typedef int EdgeType;  // 边的权值类型

#define MAXVEX 100       // 最大顶点数
#define MAX 0x7fffffff   // 无穷大

// 图的邻接矩阵表示
typedef struct{
    VertexType vexs[MAXVEX];          // 顶点表
    EdgeType arc[MAXVEX][MAXVEX];     // 邻接矩阵
    int numVertexes, numEdges;        // 图的当前顶点数和边数
} Graph;


/*
         0 1 2 3 4 5 6 7 8
         A B C D E F G H I
    0 A  0 10 M M M 11 M M M
    1 B  10 0 18 M M M 16 M 12
    2 C  M 18 0 22 M M M M 8
    3 D  M M 22 0 20 M 24 M 21
    4 E  M M M 20 0 26 M 7 M
    5 F  M M M M 26 0 17 M M
    6 G  M 16 M 24 M 17 0 19 M
    7 H  M M M 16 7 M M 19 M
    8 I  M 12 8 M M M M M 0
*/
void createGraph(Graph *G){
    G->numVertexes = 9;
    G->numEdges = 15;
    // 初始化邻接矩阵
    G->vexs[0] = 'A';
    G->vexs[1] = 'B';
    G->vexs[2] = 'C';
    G->vexs[3] = 'D';
    G->vexs[4] = 'E';
    G->vexs[5] = 'F';
    G->vexs[6] = 'G';
    G->vexs[7] = 'H';
    G->vexs[8] = 'I';

    for (int i = 0; i < G->numVertexes; i++){      // 初始化邻接矩阵
        for (int j = 0; j < G->numVertexes; j++){  // 初始化邻接矩阵
            if (i == j){                  
                G->arc[i][j] = 0;  // 对角线为0
            } else {
                G->arc[i][j] = MAX; // 用无穷大表示不连通
            }
        }
    }

    // 建立边(权值)
    // A-B A-F 
    G->arc[0][1] = 10;
    G->arc[0][5] = 11;

    // B-C B-G B-I
    G->arc[1][2] = 18;  
    G->arc[1][6] = 16;
    G->arc[1][8] = 12;

    // C-D C-I
    G->arc[2][3] = 22;
    G->arc[2][8] = 8;

    // D-E D-G D-H D-I
    G->arc[3][4] = 20;
    G->arc[3][6] = 24;
    G->arc[3][7] = 16;
    G->arc[3][8] = 21;

    // E-F E-H
    G->arc[4][5] = 26;
    G->arc[4][7] = 7;

    // F-G
    G->arc[5][6] = 17;

    // G-H
    G->arc[6][7] = 19;

    for (int i = 0; i < G->numVertexes; i++){
        for (int j = 0; j < G->numVertexes; j++){
            G->arc[j][i] = G->arc[i][j]; // 无向图邻接矩阵对称
        }
    }
}

// Prim算法，生成最小生成树
// 从顶点开始，每次选择权值最小的边，加入生成树
void Prim(Graph *G){
    int i,j,k;
    int min;                // 最小权值
    int weight[MAXVEX];     // 保存相关顶点权值(侯选边)  
    int vex_index[MAXVEX]; // 此数组下标为顶点下标，值为该顶点在生成树中的邻接顶点下标
    //举例：vex_index[1] = 0 ，假设B对应下标是1，A为顶点0，则表示B和A之间有边

    weight[0] = 0; // 初始化第一个顶点权值为0
    vex_index[0] = 0; // 初始化第一个顶点下标为0

    for (i = 1; i < G->numVertexes; i++){ // 初始化其他顶点权值为无穷大
        weight[i] = G->arc[0][i]; // 顶点0的邻接边权值
        vex_index[i] = 0;  // 顶点0下标
    }
    for (i=1; i<G->numVertexes; i++){
        min = MAX; // 初始化最小权值为无穷大
        j = 0;
        k = 0;

        // 在侯选边中选择权值最小的边
        while (j < G->numVertexes){
            if (weight[j] != 0 && weight[j] < min){ // weight[j] != 0表示该顶点不在生成树中
                min = weight[j];  // min保存当前最小权值
                k = j; // k保存权值最小的顶点下标
            }
            j++;
        }
        printf("(%c, %c) %d \n", G->vexs[vex_index[k]], G->vexs[k], min); // 输出边和权值
        weight[k] = 0; // 将该顶点加入生成树

        // 找到新接入节点的待选路径
        for(j = 1; j < G->numVertexes; j++){
            // 如果该顶点不在生成树中，且边的权值小于原权值，则更新
            if (weight[j] != 0 && G->arc[k][j] < weight[j]){
                weight[j] = G->arc[k][j]; // 更新权值
                vex_index[j] = k; // 更新邻接顶点下标
            }
    }
    }
}

int main(){
    Graph G;
    createGraph(&G);
    Prim(&G);
    return 0;
}